#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;//结点中存储的元素类型（以char为例）
typedef struct BTNode
{
  BTDataType data;//结点中存储的元素类型
  struct BTNode* left;//左指针域（指向左孩子）
  struct BTNode* right;//右指针域（指向右孩子）
}BTNode;


typedef BTNode*  QDataType;
typedef struct QListNode
{
  struct QListNode* next;
  QDataType data;
}QListNode;

typedef struct Queue
{
  QListNode* head;
  QListNode* tail;
}Queue;

//队列初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head =NULL;
  pq->tail =NULL;
}

//销毁队列
void QueueDestory(Queue* pq)
{
  assert(pq);
  QListNode* cur = pq->head;
  while(cur)
  {
    QListNode* next = cur->next;
    free(cur);
    cur= next;
  }
  pq->head = NULL;
  pq->tail = NULL;
}
// 入队列
void QueuePush(Queue* pq,QDataType x)
{
  assert(pq);
  QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
  if(newnode==NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }

  newnode->data = x;
  newnode->next = NULL;
  if(pq->head==NULL)
  {
    pq->head=pq->tail=newnode;
  }
  else 
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }

}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head==NULL;
}


//出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if(pq->head->next==NULL)
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }

  else 
  {
    QListNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }

}
//获取队列头部元素
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));

  return pq->head->data;
}
//获取尾部元素
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

//获取队列元素个数
int QueueSize(Queue* pq)
{
  assert(pq);
  QListNode* cur = pq->head;
  int count = 0;
  while(cur)
  {
    ++count;
    cur = cur->next;
  }
  return count;

}
